package wxy;

public class LeetCode300 {
    class Solution1 {
        public int lengthOfLIS(int[] nums) {
            int n = nums.length;
            int[] dp = new int[n];
            dp[0] = 1;
            for (int i = 1; i < n; i++) {
                int max = 1;
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        max = Math.max(max, dp[j] + 1);
                    }
                }
                dp[i] = max;
            }
            int max = 1;
            for (int length : dp) {
                max = Math.max(max, length);
            }
            return max;
        }
    }

    class Solution2 {
        public int lengthOfLIS(int[] nums) {
            int n = nums.length;
            int[] a = new int[n];
            a[0] = nums[0];
            int length = 1;
            for (int i = 1; i < n; i++) {
                int num = nums[i];
                if (num < a[0]) {
                    a[0] = num;
                } else if (num > a[length - 1]) {
                    a[length] = num;
                    length++;
                } else {
                    int left = 0;
                    int right = length - 1;
                    while (left < right) {
                        int mid = (left + right) / 2;
                        if (a[mid] < num) {
                            left = mid + 1;
                        } else if (a[mid] > num) {
                            right = mid;
                        } else {
                            left = mid;
                            break;
                        }
                    }
                    a[left] = num;
                }
            }
            return length;
        }
    }
}
